并不会有更好的阅读体验 甚至你在机房还访问不了
令 , 虽然不是积性函数,仍考虑线性筛。
首先考虑一个式子:
然后有:
- ,
- ,
- ,
- ,
, 点可以展开后利用上式化简。
其中 为 的最小质因子。
ps. 整除分块中 可能为 , 为了方便令 。
#include <cstdio>
#include <iostream>
using namespace std;
const int MAXN = 1e7 , Mod = 1e9 + 7;
int Quick_pow( int x , int po , int p = Mod ) {
int Ans = 1;
for( ; po ; po >>= 1 , x = 1ll * x * x % p )
if( po & 1 ) Ans = 1ll * Ans * x % p;
return Ans;
}
int Inv( int x , int p = Mod ) {
return Quick_pow( x , p - 2 );
}
int prn , prime[ MAXN + 5 ] , f[ MAXN + 5 ];
bool vis[ MAXN + 5 ];
void sieve( ) {
f[ 0 ] = 1 , f[ 1 ] = 1;
for( int i = 2 ; i <= MAXN ; i ++ ) {
if( !vis[ i ] ) { prime[ ++ prn ] = i , f[ i ] = i; }
for( int j = 1 ; j <= prn && 1ll * i * prime[ j ] <= MAXN ; j ++ ) {
vis[ i * prime[ j ] ] = 1;
if( i % prime[ j ] == 0 ) {
f[ i * prime[ j ] ] = f[ i ];
break;
}
f[ i * prime[ j ] ] = 1;
}
}
for( int i = 2 ; i <= MAXN ; i ++ ) f[ i ] = 1ll * f[ i - 1 ] * f[ i ] % Mod;
}
int Solve( int n , int m ) {
int Ans = 1 , k = min( n , m );
for( int l = 1 , r ; l <= k ; l = r + 1 ) {
r = min( n / ( n / l ) , m / ( m / l ) );
Ans = 1ll * Ans * Quick_pow( 1ll * f[ r ] * Inv( f[ l - 1 ] ) % Mod , 1ll * ( n / l ) * ( m / l ) % ( Mod - 1 ) ) % Mod;
}
return Ans;
}
int t , n , m;
int main( ) {
sieve( );
scanf("%d",&t);
while( t -- ) {
scanf("%d %d",&n,&m);
printf("%d\n", Solve( n , m ) );
}
return 0;
}